//303.区域和检索- 数组不可变
//https://leetcode.cn/problems/range-sum-query-immutable/?envType=daily-question&envId=2024-03-18
class TreeArr
{
    int ArrSum(int i)
    {
        int ret = 0;
        for (; i > 0; i -= (i & -i)) ret += tree[i];
        return ret;
    }
public:
    TreeArr(int n) :tree(n + 1),arr(n) {}
    TreeArr(vector<int>& nums):tree(nums.size() + 1),arr(nums)
    {
        int n = tree.size();
        for (int i = 1; i < n; ++i)
        {
            tree[i] += nums[i - 1];
            int next = i + (i & -i);
            if (next < n) tree[next] += tree[i];
        }
    }

    void update(int idx, int val)
    {
        int diff = val - arr[idx];
        arr[idx] = val;
        int n = tree.size();
        for (int i = idx + 1; i < n; i += (i & -i)) tree[i] += diff;
    }

    int sumRange(int left, int right) { return ArrSum(right + 1) - ArrSum(left); }

private:
    vector<int> tree;
    vector<int> arr;
};

class NumArray {
public:
    NumArray(vector<int>& nums) :ta(nums) {}

    int sumRange(int left, int right) { return ta.sumRange(left, right); }

private:
    TreeArr ta;
};